package Top200;

import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-23 9:13
 * 回溯：要求不能在同一列，且必不能在一条对角线上
 * 路径：已选择的行
 * 选择列表：当前行的每一列都是选择
 * 终止条件：遍历完最后一行
 */
public class solveNQueens51 {
    List<List<String>> res=new LinkedList<>();
    void backtrack(int n,int row,LinkedList<String> path){
        if (row==n){
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            //遍历每一列，判断其是否可以放在这个位置
            if (!isValid(n,path,row,i)) continue;
            StringBuffer rows=new StringBuffer();
            for (int j = 0; j < n; j++) {
                if (j==i){
                    rows.append('Q');
                }else {
                    rows.append('.');
                }
            }
            path.add(rows.toString());
            backtrack(n,row+1,path);
            path.removeLast();
        }
    }
    boolean isValid(int n,LinkedList<String> path,int row,int col){
        for (int i = 0; i < path.size(); i++) {
            //检查列是否冲突
            if (path.get(i).charAt(col)=='Q') return false;
        }
        //检查左上方
        for (int i = row-1,j=col-1; i >=0&&j>=0 ; i--,j--) {
            if (path.get(i).charAt(j)=='Q') return false;
        }
        //检查右上方
        for (int i = row-1,j=col+1; i >=0&&j<n ; i--,j++) {
            if (path.get(i).charAt(j)=='Q') return false;
        }
        return true;
    }

    public List<List<String>> solveNQueens(int n) {
        backtrack(n,0,new LinkedList<>());
        return res;
    }
}
